class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = {}
class Solution(object):
    def longestWord(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        tree = Node('#')
        max_len = 0
        words.sort(key=lambda x: (len(x), x))
        for word in words:
            node = tree
            m = len(word)
            for i in range(m):
                if word[i] not in node.neighbors:
                    if i == m - 1:
                        new_node = Node(word[i])
                        node.neighbors[word[i]] = new_node
                        if m > max_len:
                            max_len = m
                            max_value = word
                    else:
                        break
                else:
                    node = node.neighbors[word[i]]
        if max_len:
            return max_value
        else:
            return ''



